{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 动态规划的作业"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.1-3\n",
    "设dp[i]表示长为i的钢条最优切割方案的收益，则状态转移方程\n",
    "$$dp[i]=max(p[i],max_{1\\leq j<i}(p[j]+dp[i-j])-c)$$\n",
    "程序如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "[0, 1, 5, 8, 10, 10, 17, 17, 20, 24, 30]\n"
     ]
    }
   ],
   "source": [
    "n = int(input(\"输入长度\"))\n",
    "c = int(input(\"输入花费\"))\n",
    "p_str = input().split()\n",
    "p = [int(i) for i in p_str]\n",
    "p.insert(0, 0)\n",
    "dp = p.copy()\n",
    "for i in range(1+n):  # 　循环长度\n",
    "    for j in range(1, i):  # 循环第一次切割位点\n",
    "        dp[i] = max(dp[i], p[j]+dp[i-j]-c)\n",
    "print(dp[n])\n",
    "print(dp)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.2-1\n",
    "设P[0...n-1]存储矩阵的大小，dp[i][j]是从第i个矩阵到第j个矩阵的最优连乘解，则状态转移方程：\n",
    "$$\n",
    "dp[i][j]=\\left\\{\n",
    "\\begin{align*}\n",
    "& min_{i\\leq k<j}(dp[i][k]+dp[1+k][j]+P_{i-1}P_kP_j)\\qquad(i\\neq j)\\\\\n",
    "& 0\\qquad(i=j)\n",
    "\\end{align*}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "$\\therefore$\n",
    "dp表格如下  \n",
    "<img src=\"./images/15.2-1.png\" width=50%>    \n",
    "连乘的最小代价：2010   \n",
    "\n",
    "连乘的方案：\n",
    "$$((5 \\times 10)(10 \\times 3))(((3 \\times 12)(12 \\times 5))((5 \\times 50)(50 \\times 6)))$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.2-5\n",
    "有\n",
    "$$\n",
    "\\begin{align*}\n",
    "& \\sum_{i=1}^{n}\\sum_{j=i}^{n}R(i,j)\\\\\n",
    "& =2\\times(n\\times0+(n-1)\\times1+(n-2)\\times2+...+1\\times (n-1)+0\\times n)\\\\\n",
    "& =2\\sum_{i=0}^{n}i(n-i)\\\\ \n",
    "& \\overset{\\mathrm{def}}{=}a_n\n",
    "\\end{align*}\n",
    "$$\n",
    "下证$a_n = \\frac{n^3-n}{3}$   \n",
    "易得$a_1=0$ ,且\n",
    "$$a_n-a_{n-1}=n^2-n$$\n",
    "所以\n",
    "$$\n",
    "\\begin{align*}\n",
    "& a_n \\\\\n",
    "& = \\sum_{i=1}^{n}i^2-\\sum_{i=1}^{n}i\\\\\n",
    "& = \\frac{1}{6}n(n+1)(2n+1)-\\frac{1}{2}n(n+1)\\\\\n",
    "& = \\frac{n^3-n}{3}\n",
    "\\end{align*}\n",
    "$$\n",
    "Q.E.D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.3-6\n",
    "1. 设兑换的最优解序列为依次兑换$c[1...m]$中的货币。使用反证法，  \n",
    "$\\because$\n",
    "若$c[i...j]$($1\\leq i\\leq j\\leq m$)不是原问题子问题的最优子结构，那么设这个子问题的最优解是$c^{'}[i^{'}...j^{'}]$，把$c[i...j]$替换成$c^{'}[i^{'}...j^{'}]$，则可以生成原问题的一个更优解。这和$c[1...m]$是原问题的最优解矛盾。  \n",
    "$\\therefore$\n",
    "原问题具有最优子结构。\n",
    "2. 由于子问题没有考虑到兑换$i-1$和$i$、$j$和$1+j$货币时的佣金问题，所以可能存在子问题的一个非最优解加上两个端点的佣金后收益大于子问题的最优解。   \n",
    "$\\therefore$\n",
    "原问题不具有最优子结构。   \n",
    "Q.E.D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.4-1\n",
    "LCS的状态转移方程：\n",
    "$$dp[i][j]=\\left\\{\n",
    "    \\begin{align*}\n",
    "    & 1+dp[i-1][j-1]\\qquad(a[i]=b[j])\\\\\n",
    "    & max(dp[i][j-1],dp[i-1][j])\\qquad(a[i]\\neq b[j])\n",
    "    \\end{align*}\n",
    "    \\right.\n",
    "$$\n",
    "状态转移表：  \n",
    "<img src=\"./images/15.4-1.png\" width=50%>   \n",
    "最长公共子序列长度为6，共找到2个：  \n",
    "$（ 1, 0, 0, 1, 1, 0 ）$ 、 $（ 1, 0, 1, 0, 1, 0 ）$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.5-2\n",
    "求得的OBST如图：   \n",
    "<img src=\"./images/15.5-2.svg\" width=50%>   \n",
    "总花费：3.12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15-9\n",
    "设dp[i][j]表示从第i个切点到第j个切点的最优解。则状态转移方程：\n",
    "$$\n",
    "dp[i][j]=\\left\\{\n",
    "    \\begin{align*}\n",
    "    & min_{i\\leq k<j}(dp[i][k]+dp[k][j]+L[j]-L[i])\\qquad(j-i\\geq 2)\\\\\n",
    "    & 0\\qquad(j-i<2)\n",
    "    \\end{align*}\n",
    "    \\right.\n",
    "$$\n",
    "初始时可把dp数组下标满足$|i-j|<2$初始化成0，其余部分初始化成$\\infty$。从$len \\overset{\\mathrm{def}}{=} j-i = 2$时开始累加循环。  \n",
    "程序如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "你的输入:s=20,L=[2, 8, 10]\n",
      "最优分割用时:38\n",
      "最优分割顺序之一: 10 2 8 "
     ]
    }
   ],
   "source": [
    "s = int(input())  # 待切分的字符串的长度\n",
    "L_str = input().split()\n",
    "L = [int(i) for i in L_str]  # 切点坐标\n",
    "print(\"你的输入:s={},L={}\".format(s, L))\n",
    "L.append(s)\n",
    "L.insert(0, 0)\n",
    "dp = [[float(\"inf\") if abs(j-i) >= 2 else 0 for i in range(1+s)]\n",
    "      for j in range(1+s)]  # 初始化dp数组\n",
    "part = [[i for i in range(1+s)] for _ in range(1+s)]  # 初始化part数组，用于记录分割顺序信息\n",
    "for len_L in range(2, len(L)):  # 循环长度\n",
    "    for i in range(0, len(L)-len_L):  # 循环起始点\n",
    "        j = i + len_L\n",
    "        for k in range(i, j):  # 循环k点\n",
    "            if(dp[i][k]+dp[k][j]+L[j]-L[i] < dp[i][j]):\n",
    "                dp[i][j] = dp[i][k]+dp[k][j]+L[j]-L[i]\n",
    "                part[i][j] = k\n",
    "\n",
    "\n",
    "def print_part(L: list, part: list, left: int, right: int):\n",
    "    \"\"\"\n",
    "    递归地打印part数组\n",
    "    \"\"\"\n",
    "    if right-left >= 2:\n",
    "        print(str(L[part[left][right]]), end=\" \")\n",
    "        print_part(L, part, left, part[left][right])\n",
    "        print_part(L, part, part[left][right], right)\n",
    "\n",
    "\n",
    "print(\"最优分割用时:{}\".format(dp[0][len(L)-1]))\n",
    "print(\"最优分割顺序之一:\", end=\" \")\n",
    "print_part(L, part, 0, len(L)-1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15-11\n",
    "设dp[i][j]表示从1到i月共计j需求的最优情况。进行动态规划时，我们需要枚举1~D。   \n",
    "状态转移方程：\n",
    "$$\n",
    "dp[i][j] = \\left\\{\n",
    "    \\begin{align*}\n",
    "    &　min_{0\\leq k \\leq j-D_{i-1}}w_k[i][j]\\qquad(i>1)\\\\\n",
    "    & dp[1][j]\\qquad(i=1)\n",
    "    \\end{align*}\n",
    "    \\right.\n",
    "$$\n",
    "其中，$w_k[i][j]$是成本的计算公式，由题意得\n",
    "$$\n",
    "w_k[i][j] = \\left\\{\n",
    "    \\begin{align*}\n",
    "    & w[i-1][j-k]+h(j-D_i)\\qquad(k\\leq m)\\\\\n",
    "    & w[i-1][j-k]+h(j-D_i)+c(k-m)\\qquad(k>m)\n",
    "    \\end{align*}\n",
    "    \\right.\n",
    "$$\n",
    "这样的动态规划算法的时间复杂度:$O(nD^2)$   \n",
    "由于题目未给h的具体表达式，代码不能运行，代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(a):\n",
    "    pass\n",
    "\n",
    "\n",
    "def plan(d: list, c, m, h):\n",
    "    \"\"\"\n",
    "    d:每月的需求\n",
    "    c:额外生产成本\n",
    "    m:计划内的最大生产能力\n",
    "    h:储存成本\n",
    "    \"\"\"\n",
    "    dp = [[0 for _ in range(10000)] for _ in range(10000)]\n",
    "    D = [0 if i != 0 else d[0] for i in range(len(d))]\n",
    "    for i in range(2, len(d)):  # 求解d前缀和计算D\n",
    "        D[i] = d[i]+D[i-1]\n",
    "    for i in range(1, n):\n",
    "        for j in D[i:]:\n",
    "            if i == 1:  # 对i=1特判\n",
    "                dp[i][j] = h(j-D[1])\n",
    "                if j > m:\n",
    "                    dp[i][j] += c(j-m)\n",
    "            else:\n",
    "                dp[i][j] = float(\"inf\")\n",
    "                for k in range(j-D[i-1]):\n",
    "                    temp = dp[i-1, j-k]+h(j-D[i])\n",
    "                    if k > m:\n",
    "                        temp += c*(k-m)\n",
    "                    if temp < dp[i][j]:\n",
    "                        dp[i][j] = temp\n",
    "\n",
    "    return dp\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2 (tags/v3.10.2:a58ebcc, Jan 17 2022, 14:12:15) [MSC v.1929 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
